package com.example.targetOffer.domain;

import java.util.LinkedList;

/**
 * @describe: 1.单一的栈由于栈的特性，获取最小值需要遍历对比所有元素，复杂度为O(N)，
 * 故采用建立辅助栈保存主栈不同时期最小值的方式，以空间来换取时间，达到O(1)的查找效率。
 */
public class MinStack {
    private final LinkedList<Integer> stack1;
    private final LinkedList<Integer> stack2;

    public MinStack() {
        stack1 = new LinkedList<>();
        stack2 = new LinkedList<>();
    }

    public void push(int x) {
        stack1.push(x);
        /** 必须是>=，因为主栈如果是0，1，0时执行pop，辅助栈如果是>的逻辑就会空栈，而主栈还有一个0*/
        if (stack2.isEmpty() || stack2.peek() >= x) {
            stack2.push(x);
        }
    }

    /** 注意null的细节*/
    public void pop() {
        //若当前要删除的主栈元素是当前最小元素，则辅助栈需要同步删除（因为辅助栈的主功能就是维护主栈的最小值）
        if (stack2.peek() != null && stack2.peek().equals(stack1.pop())) {
            stack2.pop();
        }
    }
    /** 注意null的细节 以及 Integer默认值是null，而int默认值是0；*/
    public Integer top() {
        return stack1.peek();
    }
    public Integer min() {
        return stack2.peek();
    }
}
